
; define a helper class that represents a sub-sequence
; within this context with sum book keeping.
(defclass sub-sequence ()
  ((sum :initform 0
	:initarg :sum
	:accessor get-sum
	:type number
	:documentation "The sum of this sequence")
   (sequence :initform nil
	     :initarg :sub-sequence
	     :accessor get-sequence
	     :type list
	     :documentation "The sub-sequence")))

(defmethod get-sum ( (s sequence) )
  (slot-value s `sum))

(defmethod get-sequence ( (s sequence) )
  (slot-value s `sequence))


(defun sublist (start end l)
  (set-difference (nthcdr start l) (nthcdr (+ end 1) l)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(defun max-sum-subsequence (seq)
  
  (let ((maxsofar 0) 
	(maxendinghere 0)
	(i 0) 
	(start-index 0)
	(end-index 0)
	(rseq (make-instance `sub-sequence)))
    (loop for s in seq
       do
	 (setf maxendinghere (max (+ maxendinghere s) 0))
	 
	 ;store the start index of the sub sequence
	 (if (eql maxendinghere 0)
	     (setf start-index (+ i 1)))
	 
	 ;store the end index of the sub sequence
	 (if (> maxendinghere maxsofar)
	     (setf end-index i))
	 
	 (setf maxsofar (max maxsofar maxendinghere))
	 
	 (setf i (+ i 1)))
    (setf (get-sequence rseq) (sublist start-index end-index seq))
    (setf (get-sum rseq) maxsofar)
    rseq))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(let ((result nil) (seq nil))
  (setf seq `(1 2 -3 -4 5 6 7 44 22 -2 4 -66 33))
  (setf result  (max-sum-subsequence seq))
  (format t "SEQUENCE: ~s~%MAX SUBSEQUENCE: ~s = ~s~%~%" seq (get-sequence result) (get-sum result))

  (setf seq `(11 -5 6 -77 9 14 -5 -2 -1 4))
  (setf result  (max-sum-subsequence seq))
  (format t "SEQUENCE: ~s~%MAX SUBSEQUENCE: ~s = ~s~%~%" seq (get-sequence result) (get-sum result))

  (setf seq `(31, -41, 59, 26, -53, 58, 97, -93, -23, 84))
  (setf result  (max-sum-subsequence seq))
  (format t "SEQUENCE: ~s~%MAX SUBSEQUENCE: ~s = ~s~%~%" seq (get-sequence result) (get-sum result)))

  (setf seq `(4, 6, -6, 2))
  (setf result  (max-sum-subsequence seq))
  (format t "SEQUENCE: ~s~%MAX SUBSEQUENCE: ~s = ~s~%~%" seq (get-sequence result) (get-sum result)))

